// 思路：1. 获取数组元素最大的位数，根据位数从低位到高位进行排序
// 2. 创建0-9的桶，根据当前位数，把元素分配到对应的桶中
// 3. 返回最终排序的数组
// 时间复杂度：O((n+m) * k) , n为待排序数组的长度，m为桶的数量，k为最大数字位数
// 空间复杂度：O(n+m)，m为桶的数量
// 稳定排序算法
// 适用场景：适用于待排序元素的位数较少，且位数较小的排序，如果位数较大，则不适用

function radixSort(arr) {
    let size = String(Math.max(...arr)).length
    for (let i = 0; i < size; i++) {
        let bucketArr = new Array(10).fill(0).map(() => [])
        for (let j = 0; j < arr.length; j++) {
            bucketArr[Math.floor(arr[j] / Math.pow(10, i) % 10)].push(arr[j])            
        }     
        arr = []   
        for (let j = 0; j < bucketArr.length; j++) {
            arr.push(...bucketArr[j])            
        }
    }
    return arr
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(radixSort(arr));